FKT algoritam

FKT algoritam, nazvan po Fišeru, Kastelinu i Temperliju, računa broj savršenih uparivanja planarnog grafa u polinomijalnom vremenu. Ovaj isti zadatak je #P-kompletan i za ostale grafove. Računanjem broja uređenjih parova, čak i za planarne grafove takođe je #P-kompletno. Ključna ideja je da konvertuje problem u Pfafijan računanje koc-simetrične matrice izvedene od planarnog ugrađivanja grafa. Pfafian matrica je onda kompjuterizovana efikasno standardnim algoritmima determinante.

Istorija

Problem brojanja planarnih savršenih uparivanja ima svoje korene u statici i hemiji, gde je originalno pitanje: Ako se diatomiski molekuli apsorbuju na površini, formirajući jedan sloj, na koliko načina se oni mogu organizovati? Funkcija particionisanja je važan kvantitet koji kodira statističke osobine sistema u ravnotezi i može se koristiti kao odgovor na prethodno pitanje. Međutim izračunavanje funkcije particije direktnom primenom njenom definicije nije praktičano. Tako da bi se precizno rešio fizički sistem, neophodno je pronaći alternativnu formu funkcije particionisanja za taj pojedinačni fizički sistem koja je dovoljno jednostavna za precizno izračunavanje. Ranih 1960-tih, definicija tačno rešivog nije bila rigorozna. Informatika je obezbedila rigoroznu definiciju uvođenjem polinomijalnog vremena, koje datira od 1965. Slično tome, notacija ne baš tačno rešivog treba da odgovara #P-teskoci, koja je definisana 1979.

Druga vrsta fizičkog sistema za razmatranje je sastavljena od dimera, što je polimer sa dva atoma. Dimerni model računa broj dimerski pokrića grafa. Drugi fizički sistem za razmatranje je vezivanje H_2O molekula u obliku leda. Ovo može biti modelovano kao usmereni, 3-regularni graf kod koga orijentacije ivica na svakom čvoru ne mogu biti iste. Koliko ivica orijentacije ima ovaj model?

Motivisani fizičkim sistemima koji uključuju dimere, 1961, Kastelin i Temperli-Fišer nezavisno nalaze broj dominskog popločavanja za m-sa-n pravougaonik. Ovo je ekvivalentno broju savršenih uparivanja za m-sa-n rešetkasti graf. 1967. Kastelin je generalizovao ovaj rezultat za sve planarne grafove.

Algoritam

Objašnjenje

Glavni uvid je da svaki ne-nula rok u Pfaffianu od matrice susedstva grafa G odgovara savrsenom uparivanju. Dakle, ako neko moze da pronadje polozaj G da uskladi sve znake termina u Pfaffian (bez obzira na + ili -), onda apsolutna vrednost Pfaffiana je samo broj savrsenih uparivanja u G. FKT algoritam radi takav zadatak za planaran graf G.

Neka G=(V,E) bude neusmeren graf sa matricom susedstva A. Definisi PM(n) da bude skup particija od n elemenata u parove, zatim broj savrsenih uparivanja u G je

$\operatorname {PerfMatch} (G)=\sum _{M\in PM(|V|)}\prod _{(i,j)\in M}A_{ij}.$

U tesnoj vezi sa ovim je Pfaffian za n x n matricu A

$\operatorname {pf} (A)=\sum _{M\in PM(n)}\operatorname {sgn} (M)\prod _{(i,j)\in M}A_{ij},$

Gde je sgn(M) znak permutacije od M. Pfaffian orijentacija od G je usmeren graf H sa (1,-1,0) matricom susedstva B takvom da je pf(b)= PerfMatch(G). 1967. Kasteleyn je dokazao da su planarni grafovi efikasno podlozni racunanju pfafian orijentacije. Konkretno, za planaran graf G, neka H bude usmerena verzija G gde je neparan broj ivica orijentisano u smeru kazaljke na satu za svako lice u planarnom ugradjivanju G. Onda je H pfafian orijentacija od G.

Na kraju, za bilo koju koc-simetričnu matricu A,

$\operatorname {pf} (A)^{2}=\det(A),$

gde det(A) je determinanta od A. Ovaj rezultat je zbog Cayleya. Posto su determinante efektivno podlozne racunanju, onda je i PerfMatch(G).

Opis visokog nivoa

An example showing how the FKT algorithm finds a Pfaffian orientation.

1. Izracuna planarnu ugradnju od G
2. Izracuna spanning stablo T₁ ulaznog grafa G
3. Daje proizvoljnu orijentaciju svakoj ivici u G koja je takodje u T₁.
4. Koristi planarna ugradjivanja da stvori (neusmeren)graf T₂ sa istim skupom cvorova kao dvojni graf od G
5. Napravi ivicu u T₂ izmedju dva cvora ako su odgovarajuca
6. Za svaki list v u T₁(to nije i koren)
   1. Neka je e usamljena ivica od G u lice odgovara v koji jos nema orijentaciju
   2. Daj e orijentaciju takvu da je broj ivica orijentisanih u smeru kazaljke na satu neparan.
   3. Ukloni v od T₂.
7. Vrati apsolutnu vrednost Pfaffian od (1,-1,0) matrice susedstva G, koja je apsolutna vrednost kvadratnog korena determinante.

Generalizacija

Zbir opterecenih savrsenih uparivanja se moze izracunati pomocu Tutte matrice za matricu susedstva u poslednjem koraku.

Kuratovski teorema navodi da konačni graf je planaran ako i samo ako ne sadrzi podgraf homeomorfan K₅ (potpun graf od pet cvorova) ili K_3,3 (potpun bipartidan graf na dve particije velicine tri). Vijay Vazirani generalizovao je FKT algoritam za grafove koji ne sadrze homeomorfan podgraf za K_3,3. Od prebrojavanja savrsenih uparivanja u opstem grafu je #P-kompletan (#P-complete), neka ogranicenja ulaznog grafa su potrebna, osim ako FP , funkcijska verzija P , jednaka je #P. Prebrojavanje parova, koja su poznata као Hosoja indeks (Hosoya index), su takodje #P-kompletna cak i za planarne grafove.

Aplikacije

FKT algoritam je video siroku primenu u holografskim algoritmima(holographic algorithm) za planarne grafove preko uparivanja(matchgates). Na primer, razmotrite planaranu verziju ledenog modela gore navedenog, koja ima tehnicko ime #PL-3-NAE-SAT (gde NAE znaci "" nisu svi isti""). Valiant je nasao polinomijalno vremenski algoritam za ovaj problem, koji koristi uparivanja.

Literatura

• Baxter, R. J. (2008) [1982]. Exactly Solved Models in Statistical Mechanics (Third изд.). Dover Publications. стр. 11. ISBN 978-0-486-46271-4. Архивирано из оригинала 20. 03. 2012. г. Приступљено 31. 05. 2013. 

Spoljašnje veze

• Presentation by Ashley Montanaro about the FKT algorithm
• More history, information, and examples can be found in chapter 2 and section 5.3.2 of Dmitry Kamenetsky's PhD thesis